package listbyorder.access1001a.test1289;

import java.util.HashMap;

/**
 * @author code_yc
 * @version 1.0
 * @date 2020/8/20 17:43
 */
public class Solution3 {

    // HashMap做缓存，还是超时
    int res = Integer.MAX_VALUE;
    HashMap<String, Integer> memo = new HashMap<>();

    public int minFallingPathSum(int[][] arr) {
        if (arr == null || arr.length == 0 || arr[0].length == 0) return 0;
        int n = arr.length;
        for (int i = 0; i < n; i++) {
            res = Math.min(res, dfs(arr, 0, i, n));
        }
        return res;
    }

    private int dfs(int[][] arr, int i, int j, int n) {
        if (j < 0 || j == n) return 0;
        String s = i + "@" + j;
        if (memo.containsKey(s)) return memo.get(s);
        if (i == n - 1) {
            return arr[i][j];
        }
        int next = Integer.MAX_VALUE;
        for (int k = 0; k < n; k++) {
            if (k != j) {
                next = Math.min(next, dfs(arr, i + 1, k, n));
            }
        }
        memo.put(s, next + arr[i][j]);
        return next + arr[i][j];
    }
}
